package ee.homework.eighth;

import java.util.Arrays;
import java.util.Collections;

public class EditDistance {

	private String x;
	private String y;

	public EditDistance(String x, String y) {
		this.x = x;
		this.y = y;
	}

	public static void main(String[] args) {
		EditDistance ed = new EditDistance("managemental", "maanegaetaln");
		System.out.println("Levenshtein distance");
		System.out.println(ed.levenshteinDistance());
		System.out.println("Damerau-Levenshtein distance");
		System.out.println(ed.levenshteinDistanceTransposition());
	}

	private void print(int[][] dm) {
		boolean check = false;
		for (int i = 0; i < dm.length; i++) {
			if (!check) {
				System.out.print("\t");
				for (int k = 0; k < x.length(); k++) {
					System.out.print("\t" + x.charAt(k));
				}
				System.out.println();
				check = true;
			}
			if (i > 0) {
				System.out.print(y.charAt(i - 1) + "\t");
			} else {
				System.out.print("\t");
			}
			for (int j = 0; j < dm[i].length; j++) {
				System.out.print(dm[i][j] + "\t");
			}
			System.out.println();
		}

	}

	private int levenshteinDistance() {
		int n = x.length();
		int m = y.length();
		int[][] dm = new int[m + 1][n + 1];

		for (int i = 0; i < m + 1; i++) {
			dm[i][0] = i;
		}

		for (int i = 0; i < n + 1; i++) {
			dm[0][i] = i;
		}

		int cost;
		int insertion;
		int deletion;
		int substitution;
		for (int i = 1; i < m + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				cost = (x.charAt(j - 1) == y.charAt(i - 1)) ? 0 : 1;
				insertion = dm[i - 1][j] + 1;
				deletion = dm[i][j - 1] + 1;
				substitution = dm[i - 1][j - 1] + cost;
				dm[i][j] = Collections.min(Arrays.asList(insertion, deletion,
						substitution));
			}
		}

		print(dm);

		return dm[m][n];
	}

	private int levenshteinDistanceTransposition() {
		int n = x.length();
		int m = y.length();
		int[][] dm = new int[m + 1][n + 1];

		for (int i = 0; i < m + 1; i++) {
			dm[i][0] = i;
		}

		for (int i = 0; i < n + 1; i++) {
			dm[0][i] = i;
		}

		int cost;
		int insertion;
		int deletion;
		int substitution;
		int transposition;
		for (int i = 1; i < m + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				cost = (x.charAt(j - 1) == y.charAt(i - 1)) ? 0 : 1;
				insertion = dm[i - 1][j] + 1;
				deletion = dm[i][j - 1] + 1;
				substitution = dm[i - 1][j - 1] + cost;
				dm[i][j] = Collections.min(Arrays.asList(insertion, deletion,
						substitution));

				if (i > 1 && j > 1 && x.charAt(j - 1) == y.charAt(i - 2)
						&& x.charAt(j - 2) == y.charAt(i - 1)) {
					transposition = dm[i - 2][j - 2] + cost;
					dm[i][j] = Collections.min(Arrays.asList(dm[i][j],
							transposition));
				}
			}
		}

		print(dm);

		return dm[m][n];
	}
}
